Đĩa CD tại Hoa Kỳ[3]

1. "Believe" (bản album) – 3:59
2. "Believe" (Xenomania phối) – 4:20

Đĩa maxi tại Hoa Kỳ/Canada[3]

1. "Believe" (bản album) – 3:59
2. "Believe" (Phat 'N' Phunky Club phối) – 7:42
3. "Believe" (Club 69 Phunk Club phối) – 8:44
4. "Believe" (Almighty Definitive phối) – 7:36
5. "Believe" (Xenomania Mad Tim and the Mekon Club phối) – 9:15
6. "Believe" (Club 69 Future Anthem phối) – 9:20
7. "Believe" (Grips Heartbroken phối) – 9:12
8. "Believe" (Club 69 Future Anthem Dub) – 7:33
9. "Believe" (Club 69 Phunk Dub) – 7:04
10. "Believe" (Phat 'N' Phunky 'After Luv' Dub) – 6:22

Đĩa CD tại Úc[3]

1. "Believe" (bản album) – 3:59
2. "Believe" (Almighty Definitive phối) – 7:36
3. "Believe" (Xenomania Phối) – 4:20

Đĩa CD tại châu Âu/Anh quốc #1[3]

1. "Believe" (bản album) – 4:01
2. "Believe" (Almighty Definitive phối) – 7:38
3. "Believe" (Xenomania phối) – 4:20

Đĩa CD tại châu Âu/Anh quốc #2[3]

1. "Believe" (bản album) – 3:58
2. "Believe" (Grips Heartbroken phối) – 9:12
3. "Believe" (Club 69 Future phối) – 6:50

Đĩa CD tại Đức[3]

1. "Believe" (bản album) – 3:59
2. "Believe" (Grip's Heartbroken phối) – 9:12

Đĩa CD tại Nhật Bản[3]

1. "Believe" (bản album) – 3:59
2. "Believe" (Almighty Definitive phối) – 7:36
3. "Believe" (Grip's Heartbroken phối) – 9:12

Đĩa CD tại Mexico[3]

1. "Believe" (bản album) – 3:59
2. "Believe" (Almighty Definitive phối) – 7:36
3. "Believe" (Xenomania phối) – 4:20

Đĩa đơn cassette tại Hoa Kỳ/Anh quốc[3]

1. "Believe" (bản album) – 3:59
2. "Believe" (Xenomania phối) – 4:20

Đĩa 7" tại Hoa Kỳ[3]

1. "Believe" (bản album) – 3:59
2. "Believe" (Xenomania phối) – 4:20

Đĩa 12" tại Anh quốc[3]

1. "Believe" (Almighty Definitive phối) – 7:36
2. "Believe" (Grip's Heartbroken phối) – 9:12
3. "Believe" (Club 69 Future Anthem phối) – 6:50
4. "Believe" (Club 69 Future Anthem Dub) – 7:33